package tree.ordertraversal;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : ConstructBinaryTreeFromPreorderAndInorderTraversal
 * @Description :
 * <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/">105. 从前序与中序遍历序列构造二叉树</a>
 * @Author : chentianyu
 * @Date 2023/1/8 00:10
 */


public class ConstructBinaryTreeFromPreorderAndInorderTraversal {

    /**
     * 思路：前序遍历用于重建树，中序遍历辅助区分左右子树（通过获取左子树个数）
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) indexMap.put(inorder[i], i);

        return buildTreeHelper(preorder, indexMap, 0, preorder.length - 1, 0);
    }

    private TreeNode buildTreeHelper(int[] preorder, Map<Integer, Integer> indexMap, int preStart, int preEnd, int inStart) {
        if (preStart > preEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        int index = indexMap.get(preorder[preStart]);
        int leftSize = index - inStart;

        root.left = buildTreeHelper(preorder, indexMap, preStart + 1, preStart + leftSize, inStart);
        root.right = buildTreeHelper(preorder, indexMap, preStart + leftSize + 1, preEnd, index + 1);
        return root;
    }
}
